import unittest
from alg import Solution, TreeNode

def build_tree(lst):
    if not lst:
        return None
    root = TreeNode(lst[0])
    queue = [root]
    i = 1
    while queue and i < len(lst):
        current = queue.pop(0)
        if lst[i] is not None:
            current.left = TreeNode(lst[i])
            queue.append(current.left)
        i += 1
        if i < len(lst) and lst[i] is not None:
            current.right = TreeNode(lst[i])
            queue.append(current.right)
        i += 1
    return root

class TestPathSumIII(unittest.TestCase):
    def setUp(self):
        self.solution = Solution()

    def test_example1(self):
        root = build_tree([10,5,-3,3,2,None,11,3,-2,None,1])
        self.assertEqual(self.solution.pathSum(root, 8), 3)

    def test_example2(self):
        root = build_tree([5,4,8,11,None,13,4,7,2,None,None,5,1])
        self.assertEqual(self.solution.pathSum(root, 22), 3)

    def test_empty_tree(self):
        self.assertEqual(self.solution.pathSum(None, 10), 0)

    def test_single_node(self):
        root = TreeNode(5)
        self.assertEqual(self.solution.pathSum(root, 5), 1)
        self.assertEqual(self.solution.pathSum(root, 10), 0)

    def test_all_zero(self):
        root = build_tree([0,0,0])
        self.assertEqual(self.solution.pathSum(root, 0), 6)

if __name__ == '__main__':
    unittest.main()    